package org.example.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * 砝码称重，输入要称重的质量，输出砝码组合
 * todo:dp方式？
 */

public class WeighSolution {

    public static void main(String[] args) {
        int[] weights = {1, 3, 9, 27};
        int goal = 21;
        WeighSolution solution = new WeighSolution();
        List<Integer> res = solution.findCombination(weights, goal);
        System.out.println(res);
    }

    public List<Integer> findCombination(int[] weights, int goal) {
        List<Integer> res = new ArrayList<>();
        if (weights.length == 0) {
            return res;
        }
        doFind(weights, 0, goal, res);
        return res;
    }

    public Boolean doFind(int[] weights, int start, int goal, List<Integer> list) {
        if (start == weights.length) {
            return goal == 0;
        }
        for (int i=start;i<weights.length;i++) {
            for (int j=-1;j<=1;j++) {
                Boolean findRes = doFind(weights, i+1, goal-(j * weights[i]), list);
                if (findRes) {
                    if (j != 0) {
                        list.add(weights[i] * j);
                    }
                    return true;
                }
            }
        }
        return false;
    }
}
